In recent years, attention has been attracted to a Low-Density Parity-Check (LDPC) code as an error correction code that provides high error correction capability with a feasible computational complexity. Due to its high error correction capability and ease of implementation, an LDPC code has been adopted in an error correction encoding method for IEEE802.11n high-speed wireless LAN systems, digital broadcasting systems, and so forth.
An LDPC code is an error correction code defined by low-density parity check matrix H. An LDPC code is a block code having a block length equal to number of columns N of parity check matrix H. A random LDPC code, array LDPC code, and QC-LDPC code (QC: Quasi-Cyclic) are proposed in Non-Patent Document 1, Non-Patent Document 2, and Non-Patent Document 3, for example.
However, a characteristic of many current communication systems is that transmission information is transmitted collected together into variable-length packets and frames, as in the case of Ethernet®. A problem with applying an LDPC code, which is a block code, to a system of this kind is, for example, how to make a fixed-length LDPC code block correspond to a variable-length Ethernet® frame. With IEEE802.11n, adjustment of the length of a transmission information sequence and an LDPC code block length is performed by executing padding processing or puncturing processing on a transmission information sequence, but it is difficult to avoid a change in the coding rate and redundant sequence transmission due to padding or puncturing.
In contrast to this kind of LDPC code of block code (hereinafter referred to as “LDPC-BC: Low-Density Parity-Check Block Code”), LDPC-CC (Low-Density Parity-Check Convolutional Code) allowing encoding and decoding of information sequences of arbitrary length have been investigated (see Non-Patent Document 1 and Non-Patent Document 1, for example).
An LDPC CC is a convolutional code defined by a low-density parity-check matrix, and, as an example, parity check matrix HT[0,n] of an LDPC-CC for which coding rate of R=½ (=b/c) is shown in FIG. 1. Here, element h1(m)(t) of HT[0,n] has a value of 0 or 1. All elements other than h1(m)(t) are 0. M represents the LDPC-CC memory length, and n represents the length of an LDPC codeword. As shown in FIG. 1, a characteristic of an LDPC-CC parity check matrix is that it is a parallelogram-shaped matrix in which 1 is placed only in diagonal terms of the matrix and neighboring elements, and the bottom-left and top-right elements of the matrix are zero.
An LDPC encoder defined by parity check matrix HT[0,n] when h1(0)(t)=1 and h2(0)(t)=1 here is represented by FIG. 2. As shown in FIG. 2, an LDPC encoder is composed of M+1 shift registers of bit-length c and a modulo 2 adder. Consequently, a characteristic of an LDPC encoder is that it can be implemented with extremely simple circuitry in comparison with a circuit that performs generator matrix multiplication or an LDPC-BC encoder that performs computation based on backward (forward) substitution. Also, since the encoder in FIG. 2 is a convolutional code encoder, it is not necessary to divide an information sequence into fixed-length blocks when encoding, and an information sequence of any length can be encoded.    Non-Patent Document 1: R. G. Gallager, “Low-density parity check codes,” IRE Trans. Inform. Theory, IT-8, pp-21-28, 1962.    Non-Patent Document 2: D. J. C. Mackay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, no. 2, pp 399-431, March 1999.    Non-Patent Document 3: J. L. Fan, “Array codes as low-density parity-check codes,” proc. of 2nd Int. Symp. on Turbo Codes, pp. 543-546, September 2000.    Non-Patent Document 4: Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Trans. Inform. Theory, vol. 47, no. 7, pp 2711-2736, November 2001.    Non-Patent Document 5: A. J. Felstorom, and K. Sh. Zigangirov, “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check Matrix,” IEEE Transactions on Information Theory, Vol. 45, No. 6, pp 2181-2191, September 1999.    Non-Patent Document 6: R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello Jr., “LDPC block and convolutional codes based on circulant matrices,” IEEE Trans. Inform. Theory, vol. 50, no. 12, pp. 2966-2984, December 2004.    Non-Patent Document 7: G. Richter, M. Kaupper, and K. Sh. Zigangirov, “Irregular low-density parity-Check convolutional codes based on protographs,” Proceeding of IEEE ISIT 2006, pp 1633-1637.    Non-Patent Document 8: R. D. Gallager, “Low-Density Parity-Check Codes,” Cambridge, Mass. MIT Press, 1963.    Non-Patent Document 9: M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity-check codes based on belief propagation,” IEEE Trans. Commun., vol. 47., no. 5, pp. 673-680, May 1999.    Non-Patent Document 10: J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Yu Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288-1299, August 2005.    Non-Patent Document 11: Y. Ogawa, “Sum-product decoding of turbo codes,” M. D. Thesis, Dept. Elec. Eng., Nagaoka Univ. of Technology, February 2007.    Non-Patent Document 12: S. Lin, D. J. Jr., Costello, “Error control coding: Fundamentals and applications,” Prentice-Hall. 12.3  pp. 538-544, 13.4  pp. 640-645    Non-Patent Document 13: Tadashi Wadayama, “Low-Density Parity-Check Code and the decoding method”, Triceps., p. 26-27.    Non-Patent Document 14: A. Pusane, R. Smarandache, P. Vontobel, and D. J. Costello Jr., “On deriving good LDPC convolutional codes from QC LDPC block codes,” Proc. of IEEE ISIT 2007, pp. 1221-1225, June 2007.    Non-Patent Document 15: A. Sridharan, D. Truhachev, M. Lentmaier, D. J. Costello, Jr., K. Sh. Zigangirov, “Distance Bounds for an Ensemble of LDPC Convolutional Codes,” IEEE Transactions on Information Theory, vol. 53, no. 12, December 2007.    Non-Patent Document 16: A. Pusane, K. S. Zigangirov, and D. J. Costello Jr., “Construction of irregular LDPC convolutional codes with fast encoding,” Proc. of IEEE ICC 2006, pp. 1160-1165, June 2006.    Non-Patent Document 17: Hiroyuki Yashima, “Convolutional code and Viterbi decoding method”, Triceps., p. 20-29.    Non-Patent Document 18: R. Johannesson, and K. S. Zigangirov, “Fundamentals of convolutional coding,” IEEE Press. pp. 337-344